package two.chapter_1.c1_3;

import java.util.Iterator;

public class LinkedList<Item> implements List<Item> {
    private int size;
    private Node first;
    private Node last;

    @Override
    public void add(Item item) {
        Node node = new Node(item);
        if (!isEmpty()) {
            last.next = node;
            last = node;
        } else {
            first = last = node;
        }

        size++;
    }

    @Override
    public boolean removeLast() {
        if (isEmpty()) {
            return false;
        }
        Node node = findReciprocalSecond(first);
        node.next = null;
        last = node;
        size--;
        if (isEmpty()) {
            first = last = null;
        }
        return true;
    }

    /**
     * 删除item后的所有结点
     * @param item
     */
    @Override
    public void removeAfter(Item item) {
        Node node=findByValue(item);
        if (node!=null){
            node.next=null;
        }
    }

    /**
     * exercise 1.3.26
     * @param item
     */
    @Override
    public void removeAll(Item item) {
       while (contains(item)) {
           remove(item);
       }
    }

    public void remove(Item item){
        if (isEmpty()){
            return;
        }
        if (first.item.equals(item)){//第一个元素单独处理
            first=first.next;
            size--;
            if (isEmpty()){
                first=last=null;
            }
        }else {
            //除了删除第一个元素，其他元素都有前驱元素
            Node previousNode = findPreviousNode(first, item);
            if (previousNode != null) {
                previousNode.next = previousNode.next.next;
                size--;
            }
        }

    }
    private Node findPreviousNode(Node node,Item item){

        while (node!=null && node.next!=null && !node.next.item.equals(item)){
            node=node.next;
        }
        return node;
    }

    @Override
    public void insertAfter(Item previous, Item after) {
        Node node=findByValue(previous);
        Node afterNode=new Node(after);
        afterNode.next=node.next;
        node.next=afterNode;
    }

    private Node findByValue(Item item) {
        Node node=first;
        while (node!=null) {
            if (node.item.equals(item)){
                return node;
            }
            node = node.next;
        }
        return null;
    }

    /**
     * 找到倒数第二个node
     *
     * @param node
     * @return
     */
    private Node findReciprocalSecond(Node node) {
        while (node.next != null && node.next.next != null) {
            node = node.next;
        }
        return node;
    }

    /**
     * 删除第k个元素，那么只要找到第k-1个元素
     *
     * @param k
     * @return
     */
    @Override
    public boolean delete(int k) {
        if (isEmpty() || k > size()) {
            return false;
        }
        if(k==1){
            first=first.next;
            if (isEmpty()){
                last=null;
            }
            return true;
        }

        int pos = 1;
        Node node = first;
        while (node != null) {
            if (pos == k - 1) {//找到第k-1个
                break;
            } else {
                pos++;
                node = node.next;
            }
        }
        node.next = node.next.next;
        return true;
    }

    @Override
    public boolean contains(Item key) {
        for (Item item:this){
            if (item.equals(key)){
                return true;
            }
        }

        return false;
    }

    @Override
    public void reverse() {

        first=recusiveReverse(first);
    }

    /**
     * 递归思想反转链表
     * a -->  b ==> b --> a
     * @param node
     * @return
     */
    private Node recusiveReverse(Node node) {
       if (node==null)return null;
       if (node.next==null) return node;

       Node next=node.next;
       Node result=recusiveReverse(next);
       next.next=node;
       node.next=null;

       return result;
    }

    @Override
    public boolean isEmpty() {
        return size() == 0;
    }

    @Override
    public int size() {
        return size;
    }

    @Override
    public Iterator<Item> iterator() {
        return new Iter();
    }

    private class Node {
        Item item;
        Node next;

        public Node(Item item) {
            this.item = item;
        }
    }

    private class Iter implements Iterator<Item> {
        private Node next = first;

        @Override
        public boolean hasNext() {
            return next != null;
        }

        @Override
        public Item next() {
            Item item = next.item;
            next = next.next;
            return item;
        }

        @Override
        public void remove() {

        }
    }
}
